import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution437 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    List<List<TreeNode>> ans = new ArrayList<List<TreeNode>>();

    List<List<TreeNode>> t = new ArrayList<List<TreeNode>>();

    // 使用栈来记录路径上的点
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

    public int pathSum(TreeNode root, int targetSum) {
        if (root != null) stack.offerLast(root);
        dfs(root);
        int count = 0;
//        for(int i=0;i<ans.size();i++){
//            for(int j=0;j<ans.get(i).size();j++){
//                System.out.print(ans.get(i).get(j).val+" ");
//            }
//            System.out.println();
//        }
        for (int i = 0; i < ans.size(); i++) {
            count += count(ans.get(i), targetSum);
        }

        for (int s = 0; s < t.size(); s++) {
            for (int j = 0; j < t.get(s).size(); j++) {
                System.out.print(t.get(s).get(j).val);
            }
            System.out.println();
        }

        return count;
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        // 如果已经得到叶子结点
        if (node.left == null && node.right == null) {
            ans.add(new ArrayList<>(stack));
            return;
        } else {
            if (node.left != null) {
                stack.offerLast(node.left);
                dfs(node.left);
                stack.pollLast();
            }
            if (node.right != null) {
                stack.offerLast(node.right);
                dfs(node.right);
                stack.pollLast();
            }
        }
    }

    public int count(List<TreeNode> path, int targetSum) {
        int count = 0;
        for (int i = 0; i < path.size(); i++) {
            long sum = 0;
            List<TreeNode> temp = new ArrayList<>();
            for (int j = i; j < path.size(); j++) {
                temp.add(path.get(j));
                sum += path.get(j).val;
                if (sum == targetSum) {
                    if (t.lastIndexOf(temp) == -1) {
                        count++;
                        t.add(temp);
                    }
                    break;
                }
            }
        }
        long sum = 0;
        List<TreeNode> temp = new ArrayList<>();
        for (int i = 0; i < path.size(); i++) {
            temp=new ArrayList<>();
            for (int j = i; j < path.size(); j++) {
                temp.add(path.get(j));
                sum += path.get(j).val;
            }
            if (sum == targetSum) {
                if (t.lastIndexOf(temp) == -1) {
                    count++;
                    t.add(temp);
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution437 s = new Solution437();
        //System.out.println(s.count(new int[]{1,2,3,2},4));
    }
}
